#ifndef PERMUTATION_UTILS_HPP
#define PERMUTATION_UTILS_HPP

#include <vector>
#include <math.h>
#include <string>
#include <iostream>

class PermutationUtils {

    typedef std::vector<int>::iterator vec_int_it;

public:
    static int * getNthPermutation(int sizeOfPermutation, int nth) {
        std::vector<int> outputPermutationInVector;

        int remain = nth - 1;
        std::vector<int> permutation;

        for (int i = 0; i < sizeOfPermutation; i++) {
            permutation.push_back(i);
        }

        for (int i = 1; i < sizeOfPermutation; i++) {
            int j = remain / factorial(sizeOfPermutation - i);
            remain = remain % factorial(sizeOfPermutation - i);
            outputPermutationInVector.push_back(permutation.at(j));

            vec_int_it it = permutation.begin();
            std::advance(it, j);
            permutation.erase(it);

            if (remain == 0) {
                break;
            }
        }

        for (int i = 0; i < permutation.size(); i++) {
            outputPermutationInVector.push_back(permutation.at(i));
        }

        int * outputPermutation = new int[sizeOfPermutation];
        vec_int_it it_begin = outputPermutationInVector.begin();
        vec_int_it it_end = outputPermutationInVector.end();
        int indexCounter = 0;
        for(vec_int_it iter = it_begin; iter  != it_end; ++iter) {
            outputPermutation[indexCounter++] = (*iter);
        }

        return outputPermutation;
    }

    static int factorial(int x) {
      return (x == 1 ? x : x * factorial(x - 1));
    }
};

#endif // PERMUTATION_UTILS_HPP
